//1. 两数之和

//暴力枚举
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(nums[i]+nums[j]==target)
                return {i,j};
            }
        }
        return {};
    }
};
//哈希表
class Solution{
public:
    vector<int>twoSum(vector<int>&nums,int target){
        unordered_map<int,int> hashtable;
        for(int i=0;i<nums.size();++i){
            auto it = hashtable.find(target-nums[i]);
            if(it!=hashtable.end()){
                return{it->second,i};
            }
            hashtable[nums[i]]=i;
        }
        return {};
    }
};


//49. 字母异位词分组
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>>mp;
        for(string&str: strs){
            string key=str;
            sort(key.begin(),key.end());
            mp[key].emplace_back(str);
        }
        vector<vector<string>>ans;
        for(auto it=mp.begin();it!=mp.end();++it){
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

// 128. 最长连续序列
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int ans=0;
        unordered_set<int> st(nums.begin(),nums.end());//把nums转成哈希集合
        for(int x:st){//遍历哈希集合
            if(st.contains(x-1)){
                continue;//如果 x - 1 存在于哈希集合中，说明 x 不是连续序列的起点，跳过
            }
            //x是序列起点
            int y=x+1;
            while(st.contains(y)){//不断寻找下一个数是否在哈希集合中
                y++;
            }
            //循环结束后，y-1是最后一个在哈希集合中的数
            ans=max(ans,y-x);//从x到y-1一共y-x个数
        }
        return ans;
    }
};